#include <bits/stdc++.h>

using namespace std;

int n,m,c[110],v[110];
long long dp[1100],ans;
void dfs(int cur,long long sum,int leave){
    if(cur==0){
        ans = max(ans ,sum);
        return;
    }
    dfs(cur-1,sum,leave);
    if(leave>=c[cur])dfs(cur-1,sum+v[cur],leave-c[cur]);
    return ;
}
int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>c[i]>>v[i];
    }
//    for(int i=1;i<=n;i++){
//        for(int j=m;j>=c[i];j--){
//            dp[j] = max(dp[j],dp[j-c[i]]+v[i]);
//        }
//    }
//    cout<<dp[m];
    dfs(n,0,m);
    cout<<ans;
    return 0;
}
